#include <iostream>
#include <cstdlib>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef int Status;
typedef int ElemType;

class SqList
{
private:
	ElemType *elem;
	int length;
	int listsize;
public:
	SqList();
	Status InitList();
	Status DestroyList();
	Status ClearList();
	Status ListEmpty();
	int ListLength();
	ElemType GetElem(int i);
	int LocateElem(ElemType e, bool (*)(ElemType, ElemType));
	ElemType PriorElem(ElemType cur_e);
	ElemType NextElem(ElemType cur_e);
	Status ListInsert(ElemType e, int i);
	ElemType ListDelete(int i);
	Status ListTraverse(void (*)(ElemType));
	friend Status InsertSort(SqList &);
	friend Status SwapSort(SqList &);
	friend Status SelectSort(SqList &);
	friend Status MergeSort(SqList &, int, int);
	friend Status QuickSort(SqList &, int, int);
	friend Status HeapSort(SqList &);
	friend void MaxHeapify(SqList &, int, int);
};

SqList::SqList()
{
	InitList();
}

Status SqList::InitList()
{
	this->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if(!this->elem)
		exit(OVERFLOW);
	this->length = 0;
	this->listsize = LIST_INIT_SIZE;
	return OK;
}

Status SqList::DestroyList()
{
	this->length = 0;
	this->listsize = 0;
	if(this->elem)
		free(this->elem);
	else
		return ERROR;
	return OK;
}

Status SqList::ClearList()
{
	if(!this->elem)
		return INFEASIBLE;
	free(this->elem);
	this->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if(!this->elem)
		exit(OVERFLOW);
	this->length = 0;
	this->listsize = LIST_INIT_SIZE;
	return OK;
}

Status SqList::ListEmpty()
{
	return this->length == 0;
}

int SqList::ListLength()
{
	return this->length;
}

ElemType SqList::GetElem(int i)
{
	if(i > this->length)
		exit(OVERFLOW);
	else if(i <= 0)
		exit(INFEASIBLE);
	return this->elem[i-1];
}

int SqList::LocateElem(ElemType e, bool (*func)(ElemType, ElemType))
{
	for(int i = 0; i <= this->length - 1; i++)
		if((*func)(this->elem[i], e))
			return i+1;
	return 0;
}

ElemType SqList::PriorElem(ElemType cur_e)
{
	for(int i = 1; i < this->length; i++)
		if(this->elem[i] == cur_e)
			return this->elem[i-1];
	exit(ERROR);
}

ElemType SqList::NextElem(ElemType cur_e)
{
	for(int i = 0; i < this->length-1; i++)
		if(this->elem[i] == cur_e)
			return this->elem[i+1];
	exit(ERROR);
}

Status SqList::ListInsert(ElemType e, int i = -127)
{
	if(i == -127)
		i = this->length + 1;
	if(i < 1 || i > this->length + 1)
		return ERROR;
	if(this->length >= this->listsize)
	{
		ElemType* newbase;
		newbase = (ElemType *)realloc(this->elem, (this->listsize + LISTINCREMENT) *  sizeof(ElemType));
		if(!newbase)
			exit(OVERFLOW);
		this->listsize += LISTINCREMENT;	
	}
	int *q = &(this->elem[i-1]);
	for(int *p = &(this->elem[this->length - 1]); p >= q; p--)
		*(p + 1) = *p;
	*q = e;
	this->length++;
	return OK;
}

ElemType SqList::ListDelete(int i)
{
	ElemType temp;
	int t;
	if(i < 1 || i > this->length)
		exit(ERROR);
	temp = this->elem[i-1];
	for(t = i-1; t < this->length; t++)
		this->elem[t] = this->elem[t+1];
	this->length--;
	return temp;
}

Status SqList::ListTraverse(void (*func)(ElemType))
{
	for(int i = 1; i <= this->length; i++)
		(*func)(this->GetElem(i));
	return OK;
}
